'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-10-05 10:34:11
'''
'''
[1, 2, 3, 10, 20, 50. 100]取出数字，和为100，可重复，总共有多少种取法。

tips:这个问题的关键在于动态规划的过程中的去重。如果我们按外层[1, n]来循环，内层types来循环，则会重复技术，例如n=3，会记录(1, 2)这种组合
以及(2,1)这种组合，这样的是重复计数。而把types这个循环放在后面，[1, n]循环放在里面，意思是先考虑type，例如先考虑有[1,2]，这个时候的计数
都是这两种组合得到的。然后再在外循环中加入5，这次是把5加入进去，不会重复考虑。
'''

class Solution:
    def numOfway(self, n):
        dp = [0]*(n+1)
        dp[0]=1
        types = [1, 2, 5, 10, 20, 50, 100]
        for t in types:
            for i in range(t, n+1):
                dp[i] += dp[i-t]
        print(dp)
        return dp[-1]
if __name__ == "__main__":
    solution = Solution()
    n = 100
    print(solution.numOfway(100))